package main

import (
	"strconv"
)

func diffWaysToCompute(expression string) []int {
	memo := make(map[string][]int)
	return dfs(expression, memo)

}

func dfs(expression string, memo map[string][]int) []int {
	if v, ok := memo[expression]; ok {
		return v
	}
	n, err := strconv.Atoi(expression)
	if err == nil {
		memo[expression] = []int{n}
		return []int{n}
	}
	res := []int{}
	for i, v := range expression {
		c := string(v)
		if c == "+" || c == "-" || c == "*" {
			lefts := dfs(expression[:i], memo)
			rights := dfs(expression[i+1:], memo)
			for _, left := range lefts {
				for _, right := range rights {
					res = append(res, compute(left, right, c))
				}
			}
		}
	}
	memo[expression] = res
	return res
}

func compute(left int, right int, op string) int {
	switch op {
	case "+":
		return left + right
	case "-":
		return left - right
	case "*":
		return left * right
	}
	return 0
}
